package com.xmotor.test_BitSit_BloomFileter;

import java.util.BitSet;

/**
 * @Description 布隆过滤器
 * @Author Dang Xianyue
 * @Date 2020-08-04 23:35
 * @Version 1.0
 */
public class BloomFileter {

    //使用加法hash算法，所以定义了一个8个元素的质数数组
    private static final int[] primes = new int[]{2, 3, 5, 7, 11, 13, 17, 19};

    //用八个不同的质数，相当于构建8个不同哈希算法
    private Hash[] hashList = new Hash[primes.length];

    //创建一个长度为10亿的比特位
    private BitSet bits = new BitSet(256 << 22);

    public BloomFileter() {
        for (int i = 0; i < primes.length; i++) {
            //使用8个质数，创建八种算法
            hashList[i] = new Hash(primes[i]);
        }
    }

    //添加元素
    public void add(String value) {
        for (Hash f : hashList) {
            //在8个哈希算法计算出的index位上设为true
            bits.set(f.hash(value), true);
        }
    }

    //判断是否在布隆过滤器中
    public boolean contains(String value) {
        if (value == null) {
            return false;
        }
        boolean ret = true;
        for (Hash f : hashList) {
            //查看8个比特位上的值，当所有位都为是true是就在过滤器中
            ret = ret && bits.get(f.hash(value));
        }
        return ret;
    }

}
